# 给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。 
# 
#  
# 
#  示例 1: 
# 
#  
# Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
# Output: [3,9,20,null,null,15,7]
#  
# 
#  示例 2: 
# 
#  
# Input: preorder = [-1], inorder = [-1]
# Output: [-1]
#  
# 
#  
# 
#  提示: 
# 
#  
#  1 <= preorder.length <= 3000 
#  inorder.length == preorder.length 
#  -3000 <= preorder[i], inorder[i] <= 3000 
#  preorder 和 inorder 均无重复元素 
#  inorder 均出现在 preorder 
#  preorder 保证为二叉树的前序遍历序列 
#  inorder 保证为二叉树的中序遍历序列 
#  
#  Related Topics 树 数组 哈希表 分治 二叉树 
#  👍 1253 👎 0


from typing import List


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def build(preorder_left, preorder_right, inorder_left, inorder_right):
            if preorder_left > preorder_right:
                return None
            root_val = preorder[preorder_left]
            root_index = inorder_index[root_val]
            r = TreeNode(root_val)
            left_len = root_index - inorder_left
            r.left = build(preorder_left + 1, preorder_left + left_len, inorder_left, root_index - 1)
            r.right = build(preorder_left + left_len + 1, preorder_right, root_index + 1, inorder_right)
            return r
        inorder_index = {val: i for i, val in enumerate(inorder)}
        n = len(preorder)
        return build(0, n - 1, 0, n-1)


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


# 广度优先遍历树
def bfs_tree(r: TreeNode) -> List[int]:
    ans = []
    q = [r]
    while q:
        node = q.pop(0)
        ans.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    return ans


# Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
# inorder_index = 1
# left_length = 1
#
# Output: [3,9,20,null,null,15,7]
# 3
# /\
# 9 20
#    /\
#    15 7
# 前序: [根, [左前], [右前]]
# 中序: [[左中], 根, [右中]]
# 解法1: 递归
# 在中序中定位到 根节点, 获取左右子树长度
# 左前 + 左中 构建左子树, 右前 + 右中 构建右子树, 将左右子树连接到根节点
# 0 开始的1个元素 0 + 1 -1, 即 a 开始的n 个元素, a + n -1
# python [] 既可以当栈, 又可以当队列, 队列: s.pop(0), 栈:s.pop()
#
#     def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
#         def build(preorder_left: int, preorder_right: int, inorder_left, inorder_right) -> TreeNode:
#             if preorder_left > preorder_right:
#                 return None
#             root_val = preorder[preorder_left]
#             root = TreeNode(root_val)
#             inorder_root = inorder_index[root_val]
#             left_length = inorder_root - inorder_left
#             root.left = build(preorder_left + 1, preorder_left + left_length, inorder_left, inorder_root - 1)
#             root.right = build(preorder_left + left_length + 1, preorder_right, inorder_root + 1, inorder_right)
#             return root
#
#         # 中序 {元素: 出现位置}
#         inorder_index = {e: i for i, e in enumerate(inorder)}
#         n = len(preorder)
#         return build(0, n - 1, 0, n - 1)

if __name__ == '__main__':
    s = Solution()
    preorder = [3, 9, 20, 15, 7]
    inorder = [9, 3, 15, 20, 7]
    t1 = s.buildTree(preorder, inorder)
    r1 = bfs_tree(t1)
    assert r1 == [3, 9, 20, 15, 7], r1
